home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1999 June / macpower199906.bin / 9906⁄AMUG / INTERNET / NetCacheResolver 0.9d7.sit / NetCacheResolver 0.9d7 folder / source code CWPro4 / source / NCR_Qsort.c < prev    next >
Encoding:
Text File  |  1999-02-02  |  7.7 KB  |  255 lines  |  [TEXT/CWIE]
  1. // NetCache Resolver, 1995 (C) Mizutori Tetsuya
  2. // - NCR_Qsort.c, October 18, 1995
  3. // This document is pretty printed in 10-point Geneva font.
  4.  
  5. #include "NCR_Basic.h"
  6. #include "NCR_Qsort.h"
  7. #include "NCR_Error.h"
  8. #ifdef DEBUG
  9. #include "NCR_Message.h"
  10. #endif /*DEBUG */
  11.  
  12. // prototype
  13. static void swap ( Array *a, long i, long j );
  14. static short compare ( Array *a, long i, long j, Boolean asNumber );
  15. static short compareAsNumber ( Array *a, long i, long j );
  16. static short compareAsAlphabet ( Array *a, long i, long j );
  17. static long ValueAsNumber ( unsigned char *p, long maxlen );
  18.  
  19.  
  20. // constants
  21. static unsigned char charmap[] = {
  22.     '¥000', '¥001', '¥002', '¥003', '¥004', '¥005', '¥006', '¥007',    // control
  23.     '¥010', '¥011', '¥012', '¥013', '¥014', '¥015', '¥016', '¥017',
  24.     '¥020', '¥021', '¥022', '¥023', '¥024', '¥025', '¥026', '¥027',
  25.     '¥030', '¥031', '¥032', '¥033', '¥034', '¥035', '¥036', '¥037',
  26.  
  27.     '¥040', '¥041', '¥042', '¥043', '¥044', '¥045', '¥046', '¥047',    // " !..."
  28.     '¥050', '¥051', '¥052', '¥053', '¥054', '¥055', '¥056', '¥057',    // "()*+,-./"
  29.     '¥060', '¥061', '¥062', '¥063', '¥064', '¥065', '¥066', '¥067',    // "01234567"
  30.     '¥070', '¥071', '¥072', '¥073', '¥074', '¥075', '¥076', '¥077',    // "89:;<=>?"
  31.  
  32.     '¥100', '¥141', '¥142', '¥143', '¥144', '¥145', '¥146', '¥147',    // "@A..."
  33.     '¥150', '¥151', '¥152', '¥153', '¥154', '¥155', '¥156', '¥157',    // "HI..."
  34.     '¥160', '¥161', '¥162', '¥163', '¥164', '¥165', '¥166', '¥167',    // "PQ..."
  35.     '¥170', '¥171', '¥172', '¥133', '¥134', '¥135', '¥136', '¥137',    // "XY..."
  36.  
  37.     '¥140', '¥141', '¥142', '¥143', '¥144', '¥145', '¥146', '¥147',    // "`a..."
  38.     '¥150', '¥151', '¥152', '¥153', '¥154', '¥155', '¥156', '¥157',    // "hi..."
  39.     '¥160', '¥161', '¥162', '¥163', '¥164', '¥165', '¥166', '¥167',    // "pq..."
  40.     '¥170', '¥171', '¥172', '¥173', '¥174', '¥175', '¥176', '¥177',    // "xy..."
  41.  
  42.     '¥141', '¥141', '¥143', '¥145', '¥156', '¥157', '¥165', '¥141',
  43.     '¥141', '¥141', '¥141', '¥141', '¥141', '¥143', '¥145', '¥145',
  44.     '¥145', '¥145', '¥151', '¥151', '¥151', '¥151', '¥156', '¥157',
  45.     '¥157', '¥157', '¥157', '¥157', '¥165', '¥165', '¥165', '¥165',
  46.  
  47.     '¥240', '¥241', '¥242', '¥243', '¥244', '¥245', '¥246', '¥247',
  48.     '¥250', '¥251', '¥252', '¥253', '¥254', '¥255', '¥256', '¥257',
  49.     '¥260', '¥261', '¥262', '¥263', '¥264', '¥265', '¥266', '¥267',
  50.     '¥270', '¥271', '¥272', '¥273', '¥274', '¥275', '¥276', '¥277',
  51.  
  52.     '¥300', '¥301', '¥302', '¥303', '¥304', '¥305', '¥306', '¥307',
  53.     '¥310', '¥311', '¥040', '¥141', '¥141', '¥157', '¥316', '¥317',
  54.     '¥320', '¥321', '¥322', '¥323', '¥324', '¥325', '¥326', '¥327',
  55.     '¥171', '¥171', '¥332', '¥333', '¥334', '¥335', '¥336', '¥337',
  56.  
  57.     '¥340', '¥341', '¥342', '¥343', '¥344', '¥141', '¥145', '¥141',
  58.     '¥145', '¥145', '¥151', '¥151', '¥151', '¥151', '¥157', '¥157',
  59.     '¥360', '¥157', '¥165', '¥165', '¥165', '¥365', '¥366', '¥367',
  60.     '¥370', '¥371', '¥372', '¥373', '¥374', '¥375', '¥376', '¥377',
  61. };
  62.  
  63. /***** Quick Sort *****/
  64. void quicksort ( Array *a, long left, long right, Boolean asNumber, Boolean inReverse )
  65. {
  66.     long        i, last;
  67.  
  68.     if ( left >= right ) return;
  69.     
  70.     swap( a, left, (right+left)/2 );
  71.     last = left;
  72.     for ( i=left+1; i<=right; i++ )
  73. #ifdef COMMENT
  74.         if ( inReverse ) {
  75.             for ( i=left+1; i<=right; i++ )
  76.                 if ( compare( a, left, i, asNumber ) < 0 ) swap( a, ++last, i );
  77.         } else {
  78.             for ( i=left+1; i<=right; i++ )
  79.                 if ( compare( a, left, i, asNumber ) > 0 ) swap( a, ++last, i );
  80.         }
  81. #else /* COMMENT */
  82.         if ( ((compare( a, left, i, asNumber ) > 0) ^ inReverse ) != 0 ) swap( a, ++last, i );
  83. #endif /* COMMENT */
  84.     swap( a, left, last );
  85.     quicksort( a, left, last-1, asNumber, inReverse );
  86.     quicksort( a, last+1, right, asNumber, inReverse );
  87. }
  88.  
  89. static void swap ( Array *a, long i, long j )
  90. {
  91.     ArrayPair    pair;
  92.     
  93.     pair = a->pair[i];
  94.     a->pair[i] = a->pair[j];
  95.     a->pair[j] = pair;
  96. }
  97.  
  98. static short compare ( Array *a, long i, long j, Boolean asNumber )
  99. {
  100.     if ( asNumber )
  101.         return compareAsNumber(a, i, j );
  102.     else
  103.         return compareAsAlphabet( a, i, j );
  104. }
  105.  
  106. static short compareAsAlphabet ( Array *a, long i, long j )
  107. {
  108.     register unsigned char    * cm = (unsigned char *) charmap;
  109.     register unsigned char    *d, *s;
  110.     register long        k;
  111.     long                dlen, slen, min;
  112.     short                result;
  113.  
  114.     dlen = (a->pair[i]).keywordlen;
  115.     slen = (a->pair[j]).keywordlen;
  116.     min = ( dlen < slen ? dlen : slen );
  117.  
  118.     d = ((unsigned char *) *(a->h)) + (a->pair[i]).keyword;
  119.     s = ((unsigned char *) *(a->h)) + (a->pair[j]).keyword;
  120.  
  121.     k = 0;
  122.     while ( k < min ) {
  123.         if ( cm[d[k]] != cm[s[k]] ) break;
  124.         k++;
  125.     }
  126.  
  127.     if ( k >= min )  result = dlen - slen;
  128.     else result = ((unsigned short) cm[d[k]]) - ((unsigned short)cm[s[k]]);
  129.     
  130.     return ( ( result > 0 ) ? ( 1 ) : ( result==0  ? 0 : -1 ) );
  131. }
  132.  
  133. static short compareAsNumber ( Array *a, long i, long j )
  134. {
  135.     long        dval, sval;
  136.     long        dlen, slen;
  137.     long        result;
  138.  
  139.     dlen = (a->pair[i]).keywordlen;
  140.     slen = (a->pair[j]).keywordlen;
  141.     
  142.     dval = ValueAsNumber( ((unsigned char *) *(a->h)) + (a->pair[i]).keyword, dlen );
  143.     sval = ValueAsNumber( ((unsigned char *) *(a->h)) + (a->pair[j]).keyword, slen );
  144.     
  145.     result = dval - sval;
  146.     return ( ( result > 0 ) ? ( 1 ) : ( result==0  ? 0 : -1 ) );
  147. }
  148.  
  149.  
  150. #ifdef COMMENT
  151. static short compare ( Array *a, long i, long j )
  152. {
  153.     register unsigned char    * cm = (unsigned char *) charmap;
  154.     register unsigned char    *d;
  155.     register unsigned char    *s;
  156.     short                result;
  157.  
  158.     d = ((unsigned char *) *(a->h)) + i;
  159.     s = ((unsigned char *) *(a->h)) + j;
  160.  
  161.     while ( ( *d != EOS ) && ( *s != EOS ) ) {
  162.         if ( cm[*d] != cm[*s] ) break;
  163.         ++d; ++s; }
  164.  
  165.     result = ((unsigned short) cm[*d]) - ((unsigned short)cm[*s]);
  166.     return ( (result)>0 ? 1 : ( (result)==0 ) ? 0 : -1 );
  167. }
  168. #endif /* COMMENT */
  169.  
  170. static long ValueAsNumber ( unsigned char *p, long maxlen )
  171. {
  172.     register long        s = 0;
  173.     register long        i = 0;
  174.     register unsigned char    c;
  175.     Boolean            isMinus = false;
  176.     
  177.     while ( p[i] == ' ' ) { i++; }
  178.     while ( p[i] == '-' ) { isMinus = ! isMinus; i++; }
  179.     while ( p[i] == ' ' ) { i++; }
  180.     
  181.     while ( (c=p[i]) >= '0' && c <= '9' && i < maxlen ) { s = 10*s + (c-'0'); i++; }
  182.     
  183.     if ( isMinus ) s = -s;
  184.     
  185.     return s;
  186. }
  187.  
  188. /***** Splitting Fields of Record *****/
  189. #define    EOL    '¥r'
  190. #define    TAB    '¥t'
  191. // On calling SetupFieldArray(), please set the '.fs' and '.rs' field of 'arrayH'.
  192.  
  193. long SetupFieldArray ( Handle dataH,  ArrayHandle  arrayH, short keyPosition )
  194. {
  195.     register unsigned char    *p, *q;
  196.     unsigned long    i, j, k, len;
  197.     long            datasize, count=0;
  198.     short            countKey;
  199.     short            FS = TAB, RS = EOL;
  200.     OSErr        err;
  201.  
  202.     // setup Field Separator and Record Separator
  203.     if ( ((Array *) *arrayH)->fs != '¥0' ) FS = ((Array *) *arrayH)->fs;
  204.     if ( ((Array *) *arrayH)->rs != '¥0' ) RS = ((Array *) *arrayH)->rs;
  205.     
  206.     HLock( dataH );
  207.     datasize = GetHandleSize( dataH );
  208.     p = (unsigned char *) *dataH;
  209.     
  210.     SetHandleSize( (Handle) arrayH, sizeof( Array ) );
  211.     if ( (err=MemError()) != noErr ) { ErrorMessageMEM( err, true ); }
  212.  
  213.     i = 0; count = 0;
  214.     while ( i < datasize ) {
  215.         j = i;
  216.         while ( j<datasize && p[j] != RS ) j++;
  217.         
  218.         SetHandleSize( (Handle) arrayH, GetHandleSize((Handle) arrayH)+sizeof(ArrayPair) );
  219.         if ( (err=MemError()) != noErr ) { ErrorMessageMEM( err, true ); }
  220.         
  221.         ((Array *) *arrayH)->pair[count].text = i;
  222.         ((Array *) *arrayH)->pair[count].textlen = j-i;
  223.         count++;
  224.         i = j+1;
  225.     }
  226.  
  227.     if ( count > 0 ) for ( k=0; k<count; k++ ) {
  228.         q = p + ((Array *) *arrayH)->pair[k].text;
  229.         len = ((Array *) *arrayH)->pair[k].textlen;
  230.         
  231.         if ( keyPosition <= 0 ) {
  232.             ((Array *) *arrayH)->pair[k].keyword = (q-p);
  233.             ((Array *) *arrayH)->pair[k].keywordlen = len;            
  234.         } else {
  235.             i = 0; countKey= 1;
  236.             while ( i < len && countKey < keyPosition )
  237.                 if ( q[i++] == FS ) countKey++;
  238.             j = i;
  239.             while (j < len && q[j] != FS ) j++;
  240.             ((Array *) *arrayH)->pair[k].keyword = (q-p) + i;
  241.             ((Array *) *arrayH)->pair[k].keywordlen = j-i;
  242.         }
  243.     }
  244.  
  245.   out:
  246.     ((Array *) *arrayH)->h = dataH;
  247.     ((Array *) *arrayH)->count = count;
  248.     
  249.     HUnlock( dataH );
  250.  
  251.     return count;
  252. }
  253.  
  254. // end of program
  255.